package com.lwl.shua.class02;

/**
 * @author lwl
 * @Description 公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。
 * <p>
 * 返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。
 * @date 2025/9/7 16:28
 */
public class Code04Lc1029TwoCitySchedCost {
    public int twoCitySchedCost(int[][] costs) {
        int[][] dp = new int[costs.length + 1][(costs.length / 2) + 1];
        for (int index = costs.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= costs.length / 2; rest++) {
                if (rest == 0) {
                    dp[index][rest] = dp[index + 1][rest] + costs[index][1];
                } else if (rest == costs.length - index) {
                    dp[index][rest] = dp[index + 1][rest - 1] + costs[index][0];
                } else {
                    int p1 = dp[index + 1][rest] + costs[index][1];
                    int p2 = dp[index + 1][rest - 1] + costs[index][0];
                    dp[index][rest] = Math.min(p1, p2);
                }
            }
        }
        return dp[0][costs.length / 2];
    }

    public int twoCitySchedCost2(int[][] costs) {
        return process(0, costs, costs.length / 2);
    }

    /**
     *
     * @param index 当前的人
     * @param costs 花费数组
     * @param rest  还有多少个人可以去 a 市
     * @return 剩余人飞往两座城市最低消费
     */
    private int process(int index, int[][] costs, int rest) {
        if (index == costs.length) {
            return 0;
        }
        // a 市去不了，只能选择去 b 市了
        if (rest == 0) {
            return process(index + 1, costs, rest) + costs[index][1];
        }
        // b 市去不了，只能选择去 a 市了
        if (rest == costs.length - index) {
            return process(index + 1, costs, rest - 1) + costs[index][0];
        }
        int p1 = process(index + 1, costs, rest) + costs[index][1];
        int p2 = process(index + 1, costs, rest - 1) + costs[index][0];
        return Math.min(p1, p2);
    }
}
